//给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。 
//
// 示例: 
//
// 输入: 2
//输出: 91 
//解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
// 
// Related Topics 数学 动态规划 回溯算法 
// 👍 106 👎 0

package com.leetcode.editor.cn;

//Java：计算各个位数不同的数字个数
class P357CountNumbersWithUniqueDigits {
    public static void main(String[] args) {
        Solution solution = new P357CountNumbersWithUniqueDigits().new Solution();
        // TO TEST
        System.out.println(solution.countNumbersWithUniqueDigits(9));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int countNumbersWithUniqueDigits(int n) {
            if (n == 0) {
                return 1;
            }
            int first = 10, second = 9 * 9;
            int size = Math.min(n, 10);
            for (int i = 2; i <= size; i++) {
                first += second;
                second *= 10 - i;
            }
            return first;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}